package com.lw.leetcode.arr.b;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * 433. 最小基因变化
 * 广度搜索例题
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/5 13:15
 */
public class MinMutation {

    public static void main(String[] args) {
        MinMutation test = new MinMutation();

        // 2
//        String st = "AACCGGTT";
//        String end = "AAACGGTA";
//        String[] strs = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};

        // 2
//        String st = "AAAAACCC";
//        String end = "AACCCCCC";
//        String[] strs = {"AAAACCCC", "AAACCCCC", "AACCCCCC"};

        // -1
        String st = "AAAAACCC";
        String end = "AACCCCCC";
        String[] strs = {};
        int i = test.minMutation(st, end, strs);
        System.out.println(i);

    }

    public int minMutation(String start, String end, String[] bank) {
        Set<String> set = new HashSet<>();
        List<String> a = new ArrayList<>();
        List<String> b = new ArrayList<>();
        int count = 0;
        a.add(start);
        while (true) {
            if (a.isEmpty()) {
                return -1;
            }
            for (String s : a) {
                if (s.equals(end)) {
                    return count;
                } else {
                    find(bank, set, s.toCharArray(), b);
                }
            }
            a = b;
            b = new ArrayList<>();
            count++;
        }
    }

    private void find(String[] bank, Set<String> set, char[] chars, List<String> list) {
        for (String s : bank) {
            if (set.contains(s)) {
                continue;
            }
            int length = s.length();
            int c = 0;
            for (int i = 0; i < length; i++) {
                if (chars[i] != s.charAt(i)) {
                    c++;
                }
                if (c > 1) {
                    break;
                }
            }
            if (c == 1) {
                set.add(s);
                list.add(s);
            }
        }
    }

}
